package com.fosss.a65_不用加减乘除做加法;

/**
 * @author: fosss
 * Date: 2023/3/6
 * Time: 19:14
 * Description: 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号
 * 示例：输入: a = 1, b = 1  输出: 2
 * 限制：a, b 均可能是负数或 0    结果不会溢出 32 位整数
 *
 * 思路：
 * 借助位运算，^ 亦或 ----相当于 无进位的求和；& 与 ----相当于求每位的进位数。设求a和b的和，a&b为进位数，如1&1=1，再向左移动一位，a&b<<1为进位数，如
 * 1&1<<1=2;a^b为无进位和，如1^1=0,以是否有进位为循环退出或递归结束条件
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int res = solution.add(1, 1);
        System.out.println("res = " + res);
    }

    /**
     * 位运算-递归     100%   97%
     */
    public int add2(int a, int b) {
        if (b == 0) {
            return a;
        }
        return add2(a ^ b, (a & b) << 1);
    }

    /**
     * 位运算-循环    由于计算机二进制都是用补码存储，所以正负数都可以这样做    100%  81%
     * ^ 亦或 ----相当于 无进位的求和， 想象10进制下的模拟情况：（如:19+1=20；无进位求和就是10，而非20；因为它不管进位情况）
     * & 与 ----相当于求每位的进位数， 先看定义：1&1=1；1&0=0；0&0=0；即都为1的时候才为1，正好可以模拟进位数的情况,还是想象10进制下模拟情
     * 况：（9+1=10，如果是用&的思路来处理，则9+1得到的进位数为1，而不是10，所以要用<<1向左再移动一位，这样就变为10了）；
     * 这样公式就是：（a^b) ^ ((a&b)<<1) 即：每次无进位求 + 每次得到的进位数--------我们需要不断重复这个过程，直到进位数为0为止
     */
    public int add(int a, int b) {
        //(a^b) ^ ((a&b)<<1) 即：每次无进位和 + 每次得到的进位数--------我们需要不断重复这个过程，直到进位数为0为止
        while (b != 0) {
            //先用一个变量将变化前的a,b运算记录下来
            int c = (a & b) << 1;//进位
            a = a ^ b;//无进位和
            b = c;//进位
        }
        return a;
    }

}














